In the field of computer techniques basically two different types of memories are found with regard to the access to stored data.
In case of the first type, the stored data are read by addressing a memory location within the memory by its number. Usually, such a memory chip shows separate address lines and data lines. To search data from such a memory, the exact address of this data has to be known. The addressed, stored data is then connected to the data lines. To this category of storage devices belong the random access memory (RAM) and the read only memory (ROM). Though this storage principle became common and appears nowadays in virtually every complex electronic device, the random access presents only a limited solution to the access requirements of many problems involving large amounts of data or fast access to certain data sets. For many applications, therefore, a name or object oriented approach to a memory location appears to be advantageous.
This storage principle is represented by the content addressable memories (CAM), also known as associative memories. These memories are labeled content or data driven, as they make use of the input word (keyword) to find all the information associated with that key. In general, the result of the input of an keyword is a match or coincidence indication of some stored words. The match or coincidence indication appears as activation of a matching line used for subsequent operations.
Content addressed devices allow to perform a search after a keyword in a parallel mode, in which all stored words are compared with the keyword simultaneously. Therefore, the use of CAM gives in many applications (except purely numerical) a significant gain in speed, which has to be paid on the other hand by higher costs per bit.
A special implementation of a CAM is known as functional memory (FM). The functional memory allows to set single bits of a stored word into a "don't-care" state being irrelevant to the matching or coincidence function. The bits of a word stored in a FM can, thus, take a third state, besides the logical 0 and 1. In conventional FM designs, the don't-care state is, for example, implemented by using flip-flops blocking the access to certain bits.
If the matching lines are not designed to address any following devices directly, often priority encoders follow to handle multiple matches. This is done by ordering the matches into a sequence according to a priority scheme.
CAMs have found many fields of application including protocol processing units in information networks, where a packet of data includes an address, which is used as the keyword for the CAM. The CAM, then, indicates the address to which the data are to be directed. Other applications are found in parallel processing to manage access to storage devices and processors common to all units. Further fields of application are data or demand driven computer architectures, and database engines, specially designed to handle the access to databases.
Since CAMs do have the above mentioned advantages, numerous ways of implementation have been suggested. Usually, the CAM implementation by semiconducting devices requires a special chip design resulting in a higher number of transistors per bit and a higher number of pins compared to the standard RAM devices. An advanced example of this approach is described in EP-A-0183885. However, in many cases the special design of the CAMs prevents their use in otherwise conventionally designed circuits, like programmable gate arrays.
A closer definition of the technical field of the invention is provided by the efforts to implement CAM using conventional random access memory. Examples for these methods or the resulting devices, respectively, may be found in EP-A-0228917, EP-A-0459703, or in the international application WO 90/04849. The underlying principle of these known techniques is a sequential comparison of the keyword with the stored data. The sequential comparison, however, deteriorates the speed of search, i.e. the main advantage of the content addressable memory. Therefore, the current invention does not make use of a sequential comparison of the stored words with the keyword, but is instead based on directly addressing the memory location at which an appropriate destination is stored by at least a part of the keyword. This technique, described for example by T.-B. Pei et al., IEEE INFOCOM 1991. Proceedings of the 10th Annual Joint Conference of the IEEE Computer and Communication Societies, New York, 1991,0515-0524, is appropriate due to its speed and simplicity only if the width of a keyword is small. As modern applications often demand keywords having a data width of 16 bits and more, this simple approach is no longer feasible.